Developer CD Series 2000 August: Tool Chest/Dev.CD Aug 00 TC Disk 2.toast/pc/sample code/overview/optimization tn demos/cacheline optimizer/cache.c

C/C++ Source or Header | 2000-06-23 | 4.5 KB | 166 lines

/*
    File:         cache.c

    Contains:     Cache Optimizer

    Assumptions: This code assumes that you are making aligned accesses to the cache,
                 and that your stride value maintains this alignment.  Because of this, I don't
                 deal with cases where your reads would overlap multiple cache blocks.

    Written by:     Tim Carroll

    Copyright:     Copyright (c) 1999 Apple Computer, Inc., All Rights Reserved.

                 You may incorporate this Apple sample source code into your program(s) without
                 restriction. This Apple sample source code has been provided "AS IS" and the
                 responsibility for its operation is yours. You are not permitted to redistribute
                 this Apple sample source code as "Apple sample source code" after having made
                 changes. If you're going to re-distribute the source, we require that you make
                 it clear in the source that the code was descended from Apple sample source
                 code, but that you've made changes.

*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <sioux.h>

char gTextBuffer[512];

typedef struct {
    int size;                // number of lines in each cache way
    int associativity;        // number of ways in the cache
    int highMask;            // mask range to determine which block is used.
    int lowMask;
} CacheDescription;

const int numberCaches = 3;
const unsigned long unusedTag = 0xFFFFFFFFUL;
const unsigned long maskOnes = 0xFFFFFFFFUL;

char *cacheStrings[3] =
{
    "L1 Cache",
    "L2 Cache",
    "TLB Entries"
};

/* These numbers are based on an iMac with 512K of cache */

CacheDescription cache [3] =
{
    128,8,20,26,  /* L1 */
    4096,2,14,25, /* L2 */
    64,2,14,19      /* TLB */
};

unsigned long tags[4096][8]; // array large enough to hold all tag data for any cache.


void DumpCacheTable (int stride, char *name, CacheDescription *cache);

int main(void)
{
    int stride, loop;

    printf ("Welcome to the cacheline tester.\n");
    printf ("Given a stride value, this program simulates walking through memory\n");
    printf ("and will give you an indication of how many cachelines you will be\n");
    printf ("using in the L1 and L2 caches.  It also gives an idea of the virtual\n");
    printf ("memory performance by measuring how many TLB entries your code will\n");
    printf ("use\n\n");

    while (1)
    {
        printf ("Enter the stride value you wish to test, or 0 to end:\n");

        gets( gTextBuffer );
        stride = atoi( gTextBuffer );

        if (stride < 1)
            break;
        else
        {
            for (loop = 0; loop < numberCaches; loop++)
                DumpCacheTable(stride, cacheStrings[loop], &(cache[loop]));
        }
    };

    return 0;
}

void DumpCacheTable (int stride, char *name, CacheDescription *cache)
{
    unsigned int address, block, tag;
    int loop, loop2;

    int size            = cache->size;
    int associativity    = cache->associativity;
    int highMask        = cache->highMask;
    int lowMask            = cache->lowMask;

    int    iterations, cachelines;
    float cacheUtilization;

    /* Initialize all the cache tags to our invalid value */
    for (loop = 0; loop < size; loop++)
    {
        for (loop2 = 0; loop2 < associativity; loop2++)
        {
            tags[loop][loop2] = unusedTag;
        }
    }

    /* We start to walk through the data at address 0.  We act as if we are
       just touching the byte at the address -- this allows us to ignore
       misalignment cases, where a quantity straddles two cachelines.

       We walk the list until we hit a cacheline which has all ways already
       filled with valid data.  From this point on, we would be throwing data
       out of this cache.
    */

    address = 0;
    iterations = 0;
    cachelines =0;

    do
    {
        /* calculate the cache block and tag value for the current address */
        block = (address >> (31-lowMask)) & (maskOnes >> (31+highMask-lowMask));
        tag = (address >> (32-highMask));

        /* determine if we've already put this tag into the block, or if there is
           an open tag */

        for (loop = 0; loop < associativity; loop++)
        {
            if (tags[block][loop] == tag)
            {
                /* tag is already in list, continue */
                address += stride;
                iterations += 1;
                break;
            }

            if (tags[block][loop] == unusedTag)
            {
                /* empty block, add to list */
                tags[block][loop] = tag;
                cachelines += 1;
                address += stride;
                iterations += 1;
                break;
            }
        }
        /* if the for loop falls through, we are done, and fall through here as well */

    } while (loop < associativity);

    cacheUtilization = (float) cachelines / (float) ( associativity * size) * 100.0;
    printf ("For the %s, this stride will evict your own data after %d iterations, \nusing %.0f percent of the cache\n\n",
                name, iterations, cacheUtilization);
}